package com.zp.self.module.level_4_算法练习.算法.排序;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

/**
 * @author By ZengPeng
 */
public class VIII_计数排序_O_n_add_k {
    @Test
    public void main() {
        //    arr的下标:  0 1 2 3 4 5 6 7  8   max = 12 ,min =3   bucket.len = 12-3+1=10  ; 3-3 = 0   12-3 = 9
        // bucket的下标:  0 1 2 3 4 5 6 7  8  9
//   每个下标对应的元素:  3 4 5 6 7 8 9 10 11 12
        // bucket的个数:  2 1 1 2 0 0 2 0  0  1
// bucket每个元素开始下标:0 2 3 4 6 6 6 8  8  8       这里：bucket[i] = nextIndexStart; nextIndexStart=bucket[i]+count;
        int[] orderly = {3,3,4,5,6,6,9,9,12};
        int[] arr = {5, 3, 4, 6, 3, 9, 12, 9, 6};
        for (int i = 0; i < 100; i++) {//打乱100次，验证排序的正确性
            猴子排序_量子级别.shuffle(arr);
//            System.out.println(Arrays.toString(arr));
            countSort(arr);
            Assert.assertEquals(Arrays.toString(arr), Arrays.toString(orderly));
        }
        countSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    /**
    题目：a.工厂员工按年龄排序。
          b.快速得知高考名次(按分数排序)

    分析：
         计数排序：时间：O(n+k) 、空间：O(n+k)、顺序稳定
             概述：通过max -min+1 ，得到所有数的区间 通过位图记录出现次数。
                【适合数据范围小，元素密集或重复多。且计算排序不需要比较】
             实现：
                 1. 遍历数组arr得到：max 、min，开辟位图bucket[水桶]： = new int[max - min+1] 记录每个元素的个数
                 2. 遍历数据arr：填充 bucket 每个元素的出现的次数  bucket[arr[i]]++;
                 3. 遍历bucket：计算每个元素的第一次出现下标。结束后：bucket[arr[i]] 代表第一个值为arr[i] 应该插入的下标：
                 4. 开辟新数组temp，遍历数组arr。在bucket位图中找到arr[i]的插入位置 bucket[arr[i]]++，下次插入到后面【保证顺序的稳定】
     **/
    public void countSort(int[] arr) {
        int max=arr[0],min=arr[0];
        //1.遍历数组arr得到：max 、min
        for (int numb : arr) {
            max = Math.max(max,numb);
            min = Math.min(min,numb);
        }
        //开辟位图bucket[水桶]： = new int[max - min+1] 记录每个元素的个数
        int[] bucket = new int[max - min+1];
        //2.遍历数据arr：填充bucket每个元素的个数bucket[arr[i]]++;
        for (int numb : arr)
            bucket[numb-min]++;
        //3.遍历bucket：从开头元素，累积前面每个元素次数，就是bucket[arr[i]]排序中的开始位置：
        int nextIndexStart=bucket[0];
        for (int i = 1; i < bucket.length; i++) {
            int count = bucket[i];
            bucket[i] = nextIndexStart;
            nextIndexStart=bucket[i]+count;
        }
        bucket[0]=0;
        //4.开辟新数组temp：缓存每个数值的位置
        int[] temp = new int[arr.length];
        //遍历数组arr：在bucket位图中找到arr[i]的插入位置bucket[arr[i]]++，下次插入到后面【保证顺序的稳定】
        for (int anArr : arr)
            temp[bucket[anArr - min]++] = anArr;
        System.arraycopy(temp, 0, arr, 0, temp.length);
    }
}
